package com.tgy.algorithm._经典题目01;

/**
 * 给定两个字符串s1和s2，问s2最少删除多少字符可以成为s1的子串?比如s1="abcde"，s2="axbc"返回1。s2删掉x'就是s1的子串了
 * // 时间复杂的
 * n^2 * m
 *
 */
public class _028_两个字符串转化问题 {


    public static int strDelete2Str(String one,String two) {

        if (one == null || two == null || one.length() == 0 || two.length() == 0) {
            return 0;
        }

        int oneLen = one.length();


        int minLen = Integer.MAX_VALUE;
//        doStrDelete2Str(two,one);
        for (int i = 0; i <= oneLen; i++) {
            int value = doStrDelete2Str(one.substring(i, oneLen),two);
            minLen = Math.min(minLen,value);
        }

        return minLen;
    }

    public static int doStrDelete2Str(String one,String two) {

        int oneLen = one.length();
        int twoLen = two.length();

        int[][] cache = new int[oneLen + 1][twoLen + 1];

        for (int i = 1; i <= twoLen; i++) {
            cache[0][i] = i;
        }

        for (int i = 1; i <= oneLen; i++) {
            cache[i][0] = Integer.MAX_VALUE;
        }

        char[] oneChars = one.toCharArray();
        char[] twoChars = two.toCharArray();
        int minLen = Integer.MAX_VALUE;
        for (int i = 1; i <= oneLen; i++) {
            for (int j = 1; j <= twoLen; j++) {
                cache[i][j] = Integer.MAX_VALUE;
                if (oneChars[i - 1] == twoChars[j - 1] && cache[i - 1][j - 1] != Integer.MAX_VALUE) {
                    cache[i][j] = cache[i - 1][j - 1];
                }
                if (cache[i][j - 1] != Integer.MAX_VALUE) {
                    cache[i][j] = Math.min(cache[i][j],cache[i][j - 1] +1);
                }
                if (j == twoLen) {
                    minLen = Math.min(minLen,cache[i][j]);
                }
            }
        }

        return minLen;
    }

    public static void main(String[] args) {

//        int i = doStrDelete2Str("abc", "axoc");
        int i = doStrDelete2Str("abcde", "axbc");
        System.out.println(i);
    }
}
